﻿// algorithms_learn.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
// 算法的一些学习实验，这里可能会少一些语法讲究和一些参数检查。更关注算法本身。

#include <iostream>

int run_main();

#include<vector>
#include<set>
#include<map>

using namespace std;

//class Deliver {
//  map<int, set<int>> city_to_info;
//  vector<int> city_order;
//  set<int> city_check;
//  int city_nodes;
//  int city_nodes_can;
//  int company;
//public:
//  Deliver(int city_nodes_p, const vector<int>& city_from, const vector<int>& city_to, int company_p):
//    city_nodes(city_nodes_p), company(company_p)
//  {
//    for (size_t i = 0; i < city_from.size() && i < city_to.size(); i++)
//    {
//      city_to_info[city_from[i]].insert(city_to[i]);
//      city_to_info[city_to[i]].insert(city_from[i]);
//    }
//    city_order.reserve(city_nodes);
//    CalcNodes();
//  }
//
//  vector<int> GetResult()const {
//    return city_order;
//  }
//
//  // 返回true表示结束
//  bool Run(const set<int>& currLevel, set<int>& nextLevel) {
//    for (auto iter = currLevel.begin(); iter != currLevel.end(); iter++)
//    {
//      int thisCity = *iter;
//      for (auto thisNextCityIter = city_to_info[thisCity].begin();
//        thisNextCityIter != city_to_info[thisCity].end(); ++thisNextCityIter) {
//        int thisNextCity = *thisNextCityIter;
//        if (city_check.end() != city_check.find(thisNextCity) ||
//          company == thisNextCity)
//        {
//          continue;
//        }
//        //city_order.push_back(thisNextCity);
//        city_check.insert(thisNextCity);
//        nextLevel.insert(thisNextCity);
//      }
//    }
//    //set<int> olds(city_order.begin(), city_order.end());
//    //for (auto iter = nextLevel.begin(); iter != nextLevel.end(); ++iter) {
//    //  if (olds.end() != olds.find(*iter)) continue;
//    //  city_order.push_back(*iter);
//    //}
//    city_order.insert(city_order.end(), nextLevel.begin(), nextLevel.end());
//    return city_order.size()+1 >= city_nodes_can;
//  }
//
//private:
//  void CalcNodes() {
//    if (city_to_info.empty() ||
//      city_to_info.end() == city_to_info.find(company) ||
//      city_to_info[company].empty()) {
//      city_nodes_can = 0;
//    }
//
//    set<int> can_nodes = city_to_info[company];
//    while (true) {
//      set<int> can_nodes_new;
//      for (auto iter = can_nodes.end(); iter != can_nodes.end(); ++iter)
//      {
//        can_nodes_new.insert(city_to_info[*iter].begin(), city_to_info[*iter].end());
//      }
//      int old_num = can_nodes.size();
//      can_nodes.insert(can_nodes_new.begin(), can_nodes_new.end());
//      if (can_nodes.size() == old_num)
//      {
//        break;
//      }
//    }
//    city_nodes_can = can_nodes.size();
//    //map<int,set<int>> can_nodes = city_to_info;
//    //for (auto iter = city_to_info.begin(); iter != city_to_info.end(); ++iter) {
//    //  int city_add = iter->first;
//    //  for (auto iterTo = iter->second.begin(); iterTo != iter->second.end(); ++iterTo) {
//    //    int city_check = *iterTo;
//    //    for (auto iterCheck = can_nodes.begin(); iterCheck != can_nodes.end(); ++iterCheck) {
//    //      if (iterCheck->second.end() != iterCheck->second.find(city_check)) {
//    //        iterCheck->second.insert(city_add);
//    //      }
//    //    }
//    //  }
//    //}
//    //city_nodes_can = can_nodes[company].size();
//  }
//};
//
//vector<int> order(int city_nodes, vector<int> city_from, vector<int> city_to, int company) {
//  Deliver objRun(city_nodes, city_from, city_to, company);
//
//  set<int> currLevel{ company };
//  set<int> nextLevel;
//  while (!objRun.Run(currLevel, nextLevel)) {
//    currLevel = nextLevel;
//  }
//  return objRun.GetResult();
//}



class Deliver {
  map<int, set<int>> city_to_info;
  vector<int> city_order;
  set<int> city_check;
  int city_nodes;
  int city_nodes_can;
  int company;
public:
  Deliver(int city_nodes_p, const vector<int>& city_from, const vector<int>& city_to, int company_p) :
    city_nodes(city_nodes_p), company(company_p)
  {
    for (size_t i = 0; i < city_from.size() && i < city_to.size(); i++)
    {
      city_to_info[city_from[i]].insert(city_to[i]);
      city_to_info[city_to[i]].insert(city_from[i]);
    }
    city_order.reserve(city_nodes);
    CalcNodes();
  }

  vector<int> GetResult()const {
    return city_order;
  }

  // 返回true表示结束
  bool Run(const set<int>& currLevel, set<int>& nextLevel) {
    for (auto iter = currLevel.begin(); iter != currLevel.end(); iter++)
    {
      int thisCity = *iter;
      for (auto thisNextCityIter = city_to_info[thisCity].begin();
        thisNextCityIter != city_to_info[thisCity].end(); ++thisNextCityIter) {
        int thisNextCity = *thisNextCityIter;
        if (city_check.end() != city_check.find(thisNextCity) ||
          company == thisNextCity)
        {
          continue;
        }
        //city_order.push_back(thisNextCity);
        city_check.insert(thisNextCity);
        nextLevel.insert(thisNextCity);
      }
    }
    //set<int> olds(city_order.begin(), city_order.end());
    //for (auto iter = nextLevel.begin(); iter != nextLevel.end(); ++iter) {
    //  if (olds.end() != olds.find(*iter)) continue;
    //  city_order.push_back(*iter);
    //}
    city_order.insert(city_order.end(), nextLevel.begin(), nextLevel.end());
    return city_order.size() + 1 >= city_nodes_can;
  }

private:
  void CalcNodes() { //优化
    if (city_to_info.empty() ||
      city_to_info.end() == city_to_info.find(company) ||
      city_to_info[company].empty()) {
      city_nodes_can = 0;
    }
    set<int> can_nodes = city_to_info[company];
    while (true) {
      set<int> can_nodes_new;
      for (auto iter = can_nodes.begin(); iter != can_nodes.end(); ++iter)
      {
        can_nodes_new.insert(city_to_info[*iter].begin(), city_to_info[*iter].end());
      }
      int old_num = can_nodes.size();
      can_nodes.insert(can_nodes_new.begin(), can_nodes_new.end());
      if (can_nodes.size() == old_num)
      {
        break;
      }
    }
    city_nodes_can = can_nodes.size();
    cout << city_nodes_can << endl;
  }
};

vector<int> order(int city_nodes, vector<int> city_from, vector<int> city_to, int company) {
  Deliver objRun(city_nodes, city_from, city_to, company);

  set<int> currLevel{ company };
  set<int> nextLevel;
  while (!objRun.Run(currLevel, nextLevel)) {
    currLevel = nextLevel;
  }
  return objRun.GetResult();
}

int main()
{
  //auto result = order(5, { 1,1,1,2,3 }, { 2,5,3,4,5 }, 1);
  run_main();
  //std::cout << "Hello World!\n";
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
